//地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一
//格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但
//它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？
//
//
//
// 示例 1：
//
// 输入：m = 2, n = 3, k = 1
//输出：3
//
//
// 示例 2：
//
// 输入：m = 3, n = 1, k = 0
//输出：1
//
//
// 提示：
//
//
// 1 <= n,m <= 100
// 0 <= k <= 20
//
//
// Related Topics 深度优先搜索 广度优先搜索 动态规划 👍 638 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
function movingCount(m: number, n: number, k: number): number {
    //? 检查位数相加
    const check = (m, n) => {
        return m % 10 + (m / 10 >> 0) + n % 10 + (n / 10 >> 0) <= k
    }
    //? set记录哪些走了
    const set = new Set()
    //? 深度优先遍历
    const dfs = (i, j) => {
        //? 不做记录的节点
        if (i >= m || j >= n || !check(i, j) || set.has(i + ',' + j)) {
            return 0
        }
        else {
            //? 加入set
            set.add(i + ',' + j)
            //? 递归计算总数 只往下和往右走就足够了
            return 1 + dfs(i + 1, j) + dfs(i, j + 1)
        }
    }
    return dfs(0, 0)

};
//leetcode submit region end(Prohibit modification and deletion)
